package com.simple;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "()"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "()[]{}"
 * 输出: true
 * 示例 3:
 * <p>
 * 输入: "(]"
 * 输出: false
 * 示例 4:
 * <p>
 * 输入: "([)]"
 * 输出: false
 * 示例 5:
 * <p>
 * 输入: "{[]}"
 * 输出: true
 */
public class Question20 {

    public static void main(String[] args) {
        String s = "{}()";
        System.out.println("[data] = " + isValid(s));
    }

    /**
     * 思路
     * 1. 判断字符串长度是否为偶数，不为偶数直接返回false
     * 2. 根据栈针的元素进行处理
     * 2.1 如果是左边，则进栈针
     * 2.2 如果是右边，则判断栈针尾部是否一致，不一致则返回false
     */
    private static boolean isValid(String s) {
        // 不为偶数，直接返回false
        if (s.length() % 2 == 1 || s.length() < 1) {
            return false;
        }

        Map<Character, Character> map = new HashMap<>();
        map.put('{', '}');
        map.put('[', ']');
        map.put('(', ')');

        LinkedList<Character> stack = new LinkedList<Character>() {{
            add('?');
        }};
        for (Character c : s.toCharArray()) {
            if (map.containsKey(c)) {
                stack.addLast(c);
            } else if (map.get(stack.removeLast()) != c) {
                return false;
            }
        }
        return stack.size() == 1;
    }
}
